/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

 // 二叉树中序遍历
class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
     
    // 递归
    // vector<int> inorderTraversal(TreeNode * root) {
    //     vector<int> result;
    //     traverse(root, result);
    //     return result;
    // }
    // void traverse(TreeNode * node, vector<int> &result) 
    // {
        
    //     if (node == NULL)
    //     {
    //         return;
    //     }
    //     traverse(node->left, result);
    //     result.push_back(node->val);
    //     traverse(node->right, result);
    // }
    
    // 非递归
    vector<int> inorderTraversal(TreeNode * root) {
        vector<int> result;
        stack<TreeNode*> s;
        TreeNode *tmp = root;
        while (tmp || !s.empty())
        {
            while (tmp)
            {
                s.push(tmp);
                tmp = tmp->left;
            }
            tmp = s.top();
            s.pop();
            result.push_back(tmp->val);
            tmp = tmp -> right;
        }
        return result;
    }
    
    
    // 非递归（个，不推荐）
    // void push_stack(stack<TreeNode*> &s, TreeNode *n)
    // {
    //     if (n)
    //     {
    //         s.push(n);
    //         while (n->left)
    //         {
    //             s.push(n->left);
    //             n = n-> left;
    //         }
    //     }
    // }
    
    // vector<int> inorderTraversal(TreeNode *root) 
    // {
    //     vector<int> result;
    //     stack<TreeNode*> s;
    //     push_stack(s, root);
    //     while (!s.empty())
    //     {
    //         TreeNode* tmp = s.top();
    //         s.pop();
    //         result.push_back(tmp->val);
    //         if (tmp -> right)
    //         {
    //             push_stack(s, tmp->right);
    //         }
    //     }
    //     return result;
    // }
};